from hash.Hash import Hash
# 用于二分查找，加快查找的速度，用来实现一致性Hash算法里面的查找树
import bisect


class ConsistentHash(Hash):
    """

    """

    def __init__(self, replica_number):
        super().__init__()
        self.replica_number = replica_number

    def set(self, key, value):
        """
        根据_hash函数计算key对应的hash值hash_key，根据hash_key在self.keys中查找对应的结点，并且将结点返回。
        查找逻辑：使用二分查找的方式在self.keys中查找，找到hash值大于或者等于hash_key且最靠近hash_key的结点，
        如果没有找到，则返回self.keys中的第一个结点，这样线性的self.keys就构成了一个完整的环，称为Hash环
        :param key:
        :param value:
        :return: 结点node
        """
        super().set(key, value)  # 写入操作之前的预处理
        hash_key = self._hash(key)
        index = bisect.bisect_right(self.keys, hash_key)
        if index == len(self.keys):
            node = self.nodes[self.keys[0]]
        else:
            node = self.nodes[self.keys[index]]
        node.set(key, value)  # 将key，value写入到服务器缓存中
        return node

    def get(self, key):
        """
        根据hash函数_hash计算key对应的hash值：hash_key，根据hash_key在self.keys中查找对应的结点，如果在某个结点里面
        没有找到，此时可以在结点对应的副本里面查找。
        :param key:
        :return:(node,value)
        """
        super().get(key)
        hash_key = self._hash(key)
        index = bisect.bisect_right(self.keys, hash_key)
        if index == len(self.keys):
            node = self.nodes[self.keys[0]]
        else:
            node = self.nodes[self.keys[index]]
        node, value = node.get(key)
        if value is not None:
            self.hit_number += 1
        else:
            # hash没有命中的时候，需要访问其他结点的数据，
            # 在服务器里面找到对应的key值，根据key值获取对应的value值，模拟一次数据迁移
            # 由于普通的Hash算法没有考虑到这一点，而实际环境下当Cache不命中时应当访问专门服务器内存，获取数据，更新缓存
            pass
        return node, value

    def _get_replica_node_keys(self, node_name):
        """
        根据结点名称获取该结点的所有副本结点对应的hash值
        :param node_name: 
        :return: 
        """
        return [self._hash("%s:%s" % (node_name, i)) for i in range(self.replica_number)]

    def add_node(self, node, index):
        """
        向结点列表的index位置添加结点，添加结点的同时，需要同时添加虚拟结点
        :param node:
        :param index:
        :return:
        """
        super().add_node(node, index)  # 添加结点
        virtual_node_keys = self._get_replica_node_keys(node.name)  # 获取结点对应的副本
        for virtual_node_key in virtual_node_keys:
            if virtual_node_key not in self.keys:
                self.nodes[virtual_node_key] = node
                bisect.insort(self.keys, virtual_node_key)  # 将虚拟结点的hash值插入到有序列表中

    def remove_node(self, node):
        """
        从Hash环中删除某个结点，删除该结点的同时删除结点对应的副本
        :param node:
        :return:
        """
        super().remove_node(node)
        virtual_node_keys = self._get_replica_node_keys(node.name)
        for virtual_node_key in virtual_node_keys:
            del self.nodes[virtual_node_key]
            index = bisect.bisect_left(self.keys, virtual_node_key)
            del self.keys[index]
        return node
